There are several techniques known for the production of mass patterns for integrated circuits of standard cells, however, the following art set forth is not directed to the wiring techniques between cells of VLSI systems.
U.S. Pat. No. 4,093,990 to Koller et al sets forth an exemplary method of producing mass patterns for integrated circuits composed of standard cells. The cells are first grouped in a predeterminable number of cell groups in such a way that as few connections as possible extend between the groups, and the space requirement of the individual groups is equal.
U.S. Pat. No. 3,653,070 to Hill et al sets forth a method of producing art work for a logic circuit to be fabricated by printed circuit board techniques. The art work is produced by a data processing machine programmed to run a package routing, a placement routine and a routing routine in addition to check routines.
The following U.S. Patents and Defensive Publication set forth various techniques for producing mass patterns and the like for integrated circuits. These are U.S. Pat. Nos. 3,567,914; 3,575,588; 3,601,590; 3,603,771; 3,653,071; 3,653,072; 3,654,615; 3,968,478; and Defensive Publication No. P940,020.
There are several techniques known for utilizing rectangular digital logic arrays for performing transformations on data matrices for solving wave equations, image processing problems and the like. However, there is no array processing art known to the applicants directed to semiconductor component physical design and wire routing.
U.S. Pat. No. 4,215,401 to Holsztynski et al relates to digital array processors of the type having a plurality of identical interconnected cells which perform sequential transformation operations on data matrices under the control of a central processor and more particularly to unique forms of cell construction and interconnection between the processing cells. The array processor set forth is a single instruction multiple data flow (SIMD) machine, which communicates with its 4 neighbors by sequential shift registers, thus not allowing simultaneous access. Control is centralized rather than autonomous on an individual basis as required for VLSI design. Internal nodes in the array cannot be independently selected, that is, there is no independent X/Y select mechanism. Therefore, the array of procesors described, would not be useful in VLSI or physical design.
U.S. Pat. No. 3,979,728 to Reddaway sets forth an array processor, operative as the peripheral of a conventional computer. Each processing element is organized on a bit-serial basis, with single-bit registers and a bit-addressable store, and the array is controlled by a microprogrammed main control unit. Thus, Reddaway is a SIMD machine like Holsztynski et al. Reddaway selects one row and one column in the array at a time, rather than multiple column and row selection at a given time.
SIMD processing apparatus has been described in the SOLOMON computer (Slotnick et al., Fall Joint Computer Conference 1962, page 97; Gregory et al., IEEE Transactions on Electronic Computers, Dec. 1963, page 774). This apparatus consists of an array of relatively simple processing elements, each of which is arranged to perform arithmetic operations upon input data in a bit-serial manner. A development of this is the ILLIAC IV Computer (Barnes et al., IEEE April 1972, page 369).
An article entitled, "Automatic Gate Allocation Placement and Routing" by Stephan C. Hoffman in the Computer-Aided Design of Digital Electronic Circuits and Systems, North-Holland Publishing Company, 1979, sets forth algorithms used for automatic gate allocation, placement and routing for VLSI networks. The algorithms route one net at a time and do not consider the consequences of the current path route on the routability of future paths.
According to the present invention, apparatus is set forth determining the wire routings in a VLSI circuit structure comprised of cells, in which a plurality of routes for a plurality of nets is considered concurrently, with the consequence of a given path being considered relative to the routability of other paths by performing congestion estimates. This is accomplished by a supervisory unit communicating with an array of identical multi-port processors with one processor dedicated to each cell in a VLSI chip. Each processor operating in an MIMD mode communicates simultaneously with its 4 adjacent neighborhood processors, to concurrently perform congestion estimates and to determine channel routings from one point to the next in the VLSI array, wherein a channel routing includes vertical and horizontal paths.